package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/middle-of-the-linked-list/description/
 *
 * 链表的中间节点
 *
 * 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
 *
 * 如果有两个中间结点，则返回第二个中间结点。
 *
 *
 *
 * @author hanjuntao
 * @date 2025/8/5 0005
 */
public class L_876_链表的中间节点 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l12 = new ListNode(2);
        ListNode l13 = new ListNode(3);
        ListNode l14 = new ListNode(4);
        ListNode l15 = new ListNode(5);
        l1.next = l12;
        l12.next = l13;
        l13.next = l14;
        l14.next = l15;
        ListNode listNode = middleNode(l1);
        ListNode.print(listNode);
    }

    /**
     * 思路：
     * 两次遍历
     *
     * 1. 获取链表的长度，计算中间节点的索引
     * 2. 遍历链表，找到索引对应的节点
     *
     *
     * @param head
     * @return
     */
    public static ListNode middleNode(ListNode head) {
        ListNode curr = head;

        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        int index = count / 2 + 1;

        curr = head;
        count = 0;
        while (curr != null) {
            count++;

            if (count == index) {
                return curr;
            }
            curr = curr.next;
        }

        return null;
    }
}
